/*
Source : https://leetcode.com/problems/valid-perfect-square/
Author : nflush@outlook.com
Date   : 2016-07-18
*/

/*
367. Valid Perfect Square
 ?  

Question Editorial Solution  
 My Submissions 




?Total Accepted: 7975
?Total Submissions: 21915
?Difficulty: Medium



Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt. 

Example 1: 
Input: 16
Returns: True



Example 2: 
Input: 14
Returns: False
*/

class Solution {
public:
    bool isPerfectSquare(int num) {
        if(1 >= num) return true;
        int last = num;
        int res = num/2;
        while (res < last)
        {
            last = res;
            res = (res + num / res) / 2;
        }
        return (num == res * res);
    }
};